Search for: All records

An influence diagram is a graphical model of a Bayesian decision problem that is solved by finding a strategy that maximizes expected utility. When an influence diagram is solved by variable elimination or a related dynamic programming algorithm, it is traditional to represent a strategy as a sequence of policies, one for each decision variable, where a policy maps the relevant history for a decision to an action. We propose an alternative representation of a strategy as a graph, called a strategy graph, and show how to modify a variable elimination algorithm so that it constructs a strategy graph. We consider both a classic variable elimination algorithm for influence diagrams and a recent extension of this algorithm that has more relaxed constraints on elimination order that allow improved performance. We consider the advantages of representing a strategy as a graph and, in particular, how to simplify a strategy graph so that it is easier to interpret and analyze. 

Influence diagrams are graphical models used to represent and solve decision-making problems under uncertainty. The solution of an influence diagram, a strategy, is traditionally represented by tables that map histories to actions; it can also be represented by an equivalent strategy tree. We show how to compress a strategy tree into an equivalent and more compact strategy graph, making strategies easier to interpret and understand. We also show how to compress a strategy graph further in exchange for bounded-error approximation. 

Influence diagrams are graphical models used to represent and solve decision-making problems under uncertainty. The solution of an influence diagram, a strategy, is traditionally represented by tables that map histories to actions; it can also be represented by an equivalent strategy tree. We show how to compress a strategy tree into an equivalent and more compact strategy graph, making strategies easier to interpret and understand. We also show how to compress a strategy graph further in exchange for bounded-error approximation.